#include "SingleLinkListMalloc.h"
#include <stdio.h>
Status Init_SLinkList(SLinkList* S)//初始化一个空的线性表S，只创建一个头结点;成功，返回OK，否则返回ERROR 
{
	puts("====开始初始化动态单链表S！====");
	S->head=(LinkList)malloc(sizeof(LNode));//创建一个头结点
	if(S->head!=NULL)
	{
		S->head->next=NULL;//将头结点的指针域赋NULL，因为此时只有头结点 
		S->head->data=0;//头结点的数据域不存元素，只是给定义的变量赋个初始值
		S->tail=S->head;//tail本来要指向最后最后一个结点，而目前只有一个头结点，也让它指向头结点，表示线性动态单链表空状态！ 
		S->len=0;//同时把动态单链表长度len置0
		puts("====动态单链表S初始化完成！====");
		return OK;
	}
	else
	{
		puts("动态链表初始化（创建头结点）失败！");
		return ERROR;
	}
}
void Head_Init_SLinkList(SLinkList* S)//头插法建立动态单链表S.head
{
	DataType n,k,co=0;
	LinkList q;//定义一个q指向新分配且待链入的结点
	fflush(stdin);
	printf("\n开始头插法(以f结束)：");
	while(1)
	{
		k=scanf("%d",&n);
		if(k==0)
		{
			break;
		}
		else
		{
			
			q=(LinkList)malloc(sizeof(LNode));
			if(q!=NULL)
			{
				q->data=n;//给分配的结点赋值 
				//下面开始头插法：
				q->next=S->head->next; 
				S->head->next=q;
				co++;
				(S->len)++;//单链表长度加一
				if(co==1)
				{
					S->tail=q;//由于是头插法，因此第一个插入的结点就始终都是最后一个结点，让尾指针指向它 
				}
			}
			else
			{
				puts("头插法创建元素结点失败！");
			}
		}
	}
	fflush(stdin);
}
void Tail_Init_SLinkList(SLinkList* S)//尾插法建立动态单链表S
{
	DataType n,k; 
	LinkList q;//定义一个q指向新分配且待链入的结点
	fflush(stdin);
	printf("\n开始尾插法(以f结束)：");
	while(1)
	{
		k=scanf("%d",&n);
		if(k==0)
		{
			break;
		}
		else
		{
			q=(LinkList)malloc(sizeof(LNode));
			if(q!=NULL)
			{
				q->data=n;//给分配的结点赋值 
				//下面开始头插法：
				q->next=S->tail->next; 
				S->tail->next=q;
				(S->len)++;//单链表长度加一
				S->tail=q;//让尾指针指向最后一个结点 
			} 
			else
			{
				puts("尾插法创建元素结点失败！");
			}
		}
	}
	fflush(stdin);
}
Status DestoryList(SLinkList* S)//销毁线性表S
{
	if(S->len==0)
	{
		puts("\n==开始【销毁】动态单链表S！==");	
	}
	else
	{
		puts("\n==开始【销毁】动态单链表S！==");
		LinkList p=S->head->next; //让p指向首元结点，即第一个元素; 
		LinkList q=p;//让q也指向p的所指
		while(p!=NULL)
		{
			q=p->next;//让q保存p位置所指的下一个结点 
			free(p);//释放p所指的结点
			p=q;//让p又指向q的所指 
		} 
		S->len=0;//让表长归0
		S->tail=S->head;//让尾指针指向头结点 
		S->head->next=NULL;
	} 
	free(S->head);
	S->head=NULL;
	puts("==【销毁】动态单链表S完成！==");
	return OK;
}
void ClearList(SLinkList* S)//清空线性表S,使单链表长度为0，只保留头结点，释放其他结点即可 
{
	if(S->len==0)
	{
		puts("\n==开始【清空】动态单链表S！==");
		puts("==【清空】动态单链表S完成！==");	
	}
	else
	{
		puts("\n==开始【清空】动态单链表S！==");
		LinkList p=S->head->next; //让p指向首元结点，即第一个元素; 
		LinkList q=p;//让q也指向p的所指
		while(p!=NULL)
		{
			q=p->next;//让q保存p位置所指的下一个结点 
			free(p);//释放p所指的结点
			p=q;//让p又指向q的所指 
		} 
		S->len=0;//让表长归0
		S->tail=S->head;//让尾指针指向头结点 
		S->head->next=NULL;
		puts("==【清空】动态单链表S完成！==");
	} 
}
Status IsEmptySLinkList(SLinkList* S)//若S为空表，则返回TRUE,否则返回FALSE;表若不存在，返回NOEXIST 
{
	if(S->head==NULL)
	{
		puts("======表不存在！不能判断是否为空表！======");	
		return  NOEXIST;
	} 
	if(S->len==0)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}
DataType SLinkListLength(SLinkList* S)//返回S中数据元素个数
{
	return S->len; 
}
DataType GetElem(SLinkList* S,DataType i,Pt e)//用e返回S中第i个元素的值,操作成功返回OK，否则返回ERROR
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		printf("\n当前表空，不能查询！\n",i);
		return ERROR;
	}
	if(i>SLinkListLength(S)||i<1) 
	{
		printf("\n当前查询位置%d不合法！\n",i);
		return ERROR;
	}
	LinkList p=S->head->next;
	DataType co=0; 
	while(p!=NULL)
	{
		co++;
		if(co==i)
		{
			*e=p->data; 
			return OK;
		}
		p=p->next;
	}
}
DataType LocateElem(SLinkList* S,DataType e)//返回e在S中的位置,有该数据元素则返回其位置，否则返回0
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		return ERROR;
	}
	LinkList p=S->head->next;
	DataType co=0; 
	while(p!=NULL)
	{
		co++;
		if(p->data==e)
		{
			return co;
		}
		p=p->next;
	}
	return ERROR;
}
Status PriorElem(SLinkList* S,DataType e,Pt proe)//若若e是S的数据元素，且不是第一个，则用proe返回它的前驱。操作成功返回OK,否则返回-6699
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		*proe=-6699; 
		printf("\n当前表S空，不能查询%d的前驱值！\n",e);
		return ERROR;
	}
	if(IsEmptySLinkList(S)!=TRUE&&LocateElem(S,e)==ERROR)
	{
		*proe=-6699; 
		printf("\n值%d不在表S中，无法返回其前驱值！\n",e);
		return ERROR;
	}
	if(LocateElem(S,e)==1)
	{
		*proe=-6699; 
		printf("值%d是表S第一个元素，无前驱值！\n",e);
		return ERROR;
	}
	LinkList p=S->head->next;
	DataType co=0; 
	while(p!=NULL)
	{
		co++;
		if(co==LocateElem(S,e)-1)
		{
			*proe=p->data;
			return OK;
		}
		p=p->next;
	}
}
Status NextElem(SLinkList* S,DataType e,Pt nexte)//若e是S的数据元素，且不是最后一个，则用nexte返回它的后继。操作成功返回OK,否则返回-6699
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		*nexte=-6699; 
		printf("\n当前表S空，不能查询%d的后继值！\n",e);
		return ERROR;
	}
	if(IsEmptySLinkList(S)!=TRUE&&LocateElem(S,e)==ERROR)
	{
		*nexte=-6699; 
		printf("\n值%d不在表S中，无法返回其后继值！\n",e);
		return ERROR;
	}
	if(LocateElem(S,e)==S->len)
	{
		*nexte=-6699; 
		printf("值%d是表S最后一个元素，无后继值！\n",e);
		return ERROR;
	}
	LinkList p=S->head->next;
	DataType co=0; 
	while(p!=NULL)
	{
		co++;
		if(co==LocateElem(S,e)+1)
		{
			*nexte=p->data;
			return OK;
		}
		p=p->next;
	}
}
Status SLinkListInsert(SLinkList* S,DataType i,DataType e)//在S第i个位置之前插入新的元素e，S长度加1,成功操作返回OK，否则返回ERROR
{
	if(i>SLinkListLength(S)+1||i<1)
	{
		printf("\n插入位置%d不合法，不能再插入！\n",i);
		return ERROR;
	}
	LinkList p=S->head;
	LinkList q;
	DataType co=-1; 
	q=(LinkList)malloc(sizeof(LNode));//q指向新分配的待插入元素结点; 
	if(q!=NULL)
	{
		q->data=e;
		while(p!=NULL)
		{
			co++;
			if(co==i-1)
			{
				q->next=p->next;
				p->next=q; 
				S->len++;//新插入一个元素结点，长度加一 
				if(i==SLinkListLength(S))
				{
					S->tail=q;//如果待插入的是尾结点，则让尾指针指向它 
				}
				return OK;
			}
			p=p->next;
		}
	}
	else
	{
		puts("待插入元素结点失败！");
		return ERROR;
	}
}
DataType SLinkListDelete(SLinkList* S,DataType i,Pt e)//删除S的第i个数据元素，并用e返回其值，S长度减1,操作成功返回删除的值，否则返回ERROR
{
	if(SLinkListLength(S)==0) 
	{
		printf("\n当前表S空，不能删除任何值！\n");
		return ERROR;
	}
	if(i>SLinkListLength(S)||i<1)
	{
		printf("\n删除位置%d不合法，不能删除任何值！\n",i);
		return ERROR;
	}
	LinkList p=S->head;
	LinkList q;//指向待删除元素的前一个元素 
	DataType co=-1; 
	while(p!=NULL)
	{
		co++;
		if(co==i-1)
		{
			q=p;
		}
		if(co==i)
		{
			//此时,p指向要被删除的元素 
			q->next=p->next;
			free(p); 
			S->len--;//新插入一个元素结点，长度加一 
			if(i==SLinkListLength(S))
			{
				S->tail=q;//如果待删除的是尾结点，则让尾指针指向它的前一个元素，即指向q
			}
			return OK;
		}
		p=p->next;
	}
}
Status SLinkListTraverse(SLinkList* S)//依次对LS每个数据元素调用函数,成功遍历返回OK，否则返回ERROR
{
	if(S->head==NULL)
	{
		puts("<===============线性动态单链表S已被销毁！无法遍历检查！===============>");
		return ERROR;
	}
	LinkList p=S->head->next;
	if(S->len==0)
	{
		printf("【遍历检查】|长度：%d|头结点-->NULL\n",S->len);
	}
	else
	{
		printf("【遍历检查】|长度：%d|头结点",S->len);
		while(p!=NULL)
		{
			printf("--->%d",p->data);
			p=p->next;
		}
		printf("-->NULL\n"); 
	}
	return OK;
}